package Queue.MaxPriorityQueue;

/*
    最大优先队列
    可以很方便的删除队列中的最大值，通过堆实现
 */
public class MaxPriorityQueue<T extends Comparable<T>> {

    private T[] elements;
    private int N;

    public MaxPriorityQueue(int capacity) {
        //capacity+1 是因为堆中会废弃0号索引（堆类似用数组存完全二叉树）
        //废弃了0号元素之后，N 的值和下标索引就一致了
        elements = (T[]) new Comparable[capacity + 1];
        N = 0;
    }

    private boolean isGreat(int i, int j) {
        return elements[i].compareTo(elements[j]) > 0;
    }

    private void exchange(int i, int j) {
        T t = elements[i];
        elements[i] = elements[j];
        elements[j] = t;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public T deleteMax() {
        T max = elements[1];
        exchange(1, N);
        N--;
        //删除了之后又破坏了队列，调用 sink() 调整
        sink(1);
        return max;
    }

    public void insert(T t) {
        elements[++N] = t;
        //插入新值后破坏了优先队列，调用 swim() 来调整队列
        swim(N);
    }

    //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void swim(int k) {
        //1 索引位置为根，对比完全二叉树的数组存储
        //很明显，1 位置就是最大了（大根堆）
        while (k > 1) {
            //和父节点比，父节点为 k/2
            if (isGreat(k, k / 2)) {
                exchange(k, k / 2);
            }
            k = k / 2;
        }
    }

    //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void sink(int k) {
        while (2 * k <= N) {
            int max;
            if (2 * k + 1 <= N) {
                if (isGreat(2 * k + 1, 2 * k)) {
                    max = 2 * k + 1;
                } else {
                    max = 2 * k;
                }
            } else {
                max = 2 * k;
            }
            if (isGreat(k, max)) {
                break;
            }
            exchange(k, max);
            k = max;
        }
    }
}
